#ifndef DFS_H
#define DFS_H

#include <vector>
#include <utility>
#include <iostream>
#include <atomic>
#include <stdexcept>
#include <mapbase.h>

inline std::vector<std::vector<Coord<int>>> dfs(
    std::vector<std::vector<int>> graph,
    Coord<int> start,
    Coord<int> end,
    const std::atomic<bool>& interrupt)
{
    std::vector<std::vector<Coord<int>>> result;

    if (graph.empty() || graph[0].empty()) {
        return result;
    }

    int width = graph.size();
    int height = graph[0].size();

    // 检查起点和终点是否有效
    if (start.x < 0 || start.x >= width || start.y < 0 || start.y >= height ||
        end.x < 0 || end.x >= width || end.y < 0 || end.y >= height) {
        return result;
    }

    std::vector<Coord<int>> currentPath;
    std::vector<std::vector<bool>> visited(height, std::vector<bool>(width, false));

    auto dfs_recursive = [&](auto&& self, int x, int y) -> void {
        if(interrupt.load()) throw std::runtime_error("Algorithm interrupted by user");

        visited[x][y] = true;
        currentPath.push_back({ x, y });

        // 如果到达终点，将当前路径添加到结果中
        if (x == end.x && y == end.y) {
            result.push_back(currentPath);
        }
        else {
            // 四个方向的移动
            std::vector<Coord<int>> directions = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };

            for (const auto& dir : directions) {
                int newX = x + dir.x;
                int newY = y + dir.y;

                // graph值为0表示可以走，1表示墙壁不能走
                if (newX >= 0 && newX < width && newY >= 0 && newY < height &&
                    !visited[newX][newY] && graph[newX][newY] != 1) {
                    self(self, newX, newY);
                }
            }
        }

        currentPath.pop_back();
        visited[x][y] = false;
        };
    dfs_recursive(dfs_recursive, start.x, start.y);

    return result;
}


// inline std::vector<std::vector<Coord<int>>> dfs(int width, int height, std::vector<std::vector<int>> graph)
// {
//     Coord<int> start = { -1, -1 }, end = { -1, -1 };
//     for (int i = 0; i < width; i++) {
//         for (int j = 0; j < height; j++) {
//             if (graph[i][j] == -1) start = { i,j };
//             if (graph[i][j] == -2) end = { i,j };
//         }
//     }
//     return dfs(graph, start, end);
// }


#endif